home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / grabst / create.c < prev    next >
C/C++ Source or Header  |  1990-03-06  |  16KB  |  565 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /* create.c -- routines for creating nodes and edges */
  9.  
  10. #include "attribute.h"
  11. #include "digraph.h"
  12. #include "debug.h"
  13. #include "malloc.h"
  14.  
  15. DIGRAPH *InitDigraph();
  16. short hash();
  17. NODE *create_node();
  18. int create_edge();
  19. int insert_edge();
  20. VERTEX *insert_vertex();
  21. NODE *insert_node();
  22. VNO get_vno();
  23.  
  24. char message[100];    /* error messages */
  25.  
  26. DIGRAPH* InitDigraph()
  27.   /* InitDigraph initializes the directed graph, digraph.  */
  28. {
  29.     DIGRAPH *digraph;
  30.     int i;                 /* counter */
  31.  
  32.     new(digraph, DIGRAPH);
  33.     digraph->title = (char *) malloc(256 * sizeof(char));
  34.     digraph->title[0] = '\0';
  35.     digraph->lastnode = -1;   /* no nodes yet */ 
  36.     digraph->levels = NULL;   /* no levels yet */ 
  37.     digraph->lastlevel = NULL;
  38.  
  39.     digraph->num_node_attributes = 0;
  40.     digraph->num_edge_attributes = 0;
  41.     digraph->dist_node_attribute = 0;
  42.     digraph->dist_edge_attribute = 0;
  43.     digraph->node_att_names = NULL;
  44.     digraph->edge_att_names = NULL;
  45.  
  46.     for (i = 0; i < MAXNODES; i++)
  47.     {
  48.         digraph->nodes[i] = NULL;
  49.     }
  50.  
  51.     for (i = 0; i < MAXHASH; i++)
  52.     {
  53.         digraph->hashtbl[i] = NULL;
  54.     }
  55.    
  56.     return(digraph);
  57. } /* InitDigraph */
  58.  
  59. InitNodeAttrs(digraph, attr_names, num_attr, dist_attr)
  60. DIGRAPH *digraph;
  61. char **attr_names;
  62. int num_attr, dist_attr;
  63.    /* Initialize the node user-defined attribute fields for a digraph */
  64. {
  65.     digraph->node_att_names = attr_names;
  66.     NNodeAttr(digraph) = num_attr;
  67.     DNodeAttr(digraph) = dist_attr;
  68. }
  69.  
  70. InitEdgeAttrs(digraph, attr_names, num_attr, dist_attr)
  71. DIGRAPH *digraph;
  72. char **attr_names;
  73. int num_attr, dist_attr;
  74.    /* Initialize the user-defined edge attribute fields for a digraph */
  75. {
  76.     digraph->edge_att_names = attr_names;
  77.     NEdgeAttr(digraph) = num_attr;
  78.     DEdgeAttr(digraph) = dist_attr;
  79. }
  80.  
  81. NODE *CreateNode(digraph, name, text, x_pos, y_pos)
  82. DIGRAPH *digraph;
  83. char *name;
  84. char *text;
  85. int x_pos, y_pos;
  86.   /** 
  87.      CreateNode puts in default values for shape, brush, color, 
  88.      status, level, position and the user-defined attributes, and then calls 
  89.      create_node.
  90.    **/
  91. {
  92.     SHAPE shape = DEFAULT_SHAPE;
  93.     BRUSH brush = DEFAULT_BRUSH;
  94.     COLOR color = DEFAULT_COLOR;
  95.     STATUS status = NORMAL;
  96.     LNO level = -1;
  97.     int position = -1;
  98.     NODE *node;
  99.     int i;
  100.     char **attr;
  101.  
  102.     attr = (char **) malloc(NNodeAttr(digraph) * sizeof(char *));
  103.  
  104.     for (i = 0; i < NNodeAttr(digraph); i++)
  105.     {
  106.     strsave(attr[i], NULL_STRING);
  107.     }
  108.  
  109.     dispose(attr[DNodeAttr(digraph)]);
  110.     strsave(attr[DNodeAttr(digraph)], text);
  111.     node = create_node(digraph, name, attr, shape, brush, color, TRUE, 
  112.     x_pos, y_pos, status, level, position);
  113.     return (node);
  114. } /* CreateNode */
  115.  
  116. int CreateEdge(digraph, from_node, to_node)
  117. DIGRAPH *digraph;
  118. NODE *from_node, *to_node;
  119.   /** 
  120.      CreateEdge puts in default values for the attributes and then calls 
  121.      insert_edge
  122.    **/
  123. {
  124.     int errval;        /* returns non-zero value if error */
  125.     BRUSH brush = DEFAULT_BRUSH;
  126.     COLOR color = DEFAULT_COLOR;
  127.     char **attr;
  128.     int i;
  129.  
  130.     attr = (char **) malloc(NEdgeAttr(digraph) * sizeof(char *));
  131.  
  132.     for (i = 0; i < NEdgeAttr(digraph); i++)
  133.     {
  134.     strsave(attr[i], NULL_STRING);
  135.     }
  136.  
  137.     errval = insert_edge(digraph, Vno(from_node), Vno(to_node), attr, brush,
  138.              color);
  139.     return (errval);
  140. } /* CreateEdge */
  141.  
  142. NODE *create_node(digraph, name, attr, shape, brush, color, disp, x_pos, y_pos, 
  143.     status, level, position)
  144. DIGRAPH *digraph;
  145. char *name;           /* name of node */
  146. char **attr;           /* user-defined attributes for the node */
  147. SHAPE shape;           /* shape of node */
  148. BRUSH brush;           /* how to draw it */
  149. COLOR color;           /* color to draw it */
  150. BOOL disp;           /* display it or not */
  151. int x_pos, y_pos;       /* initial x and y positions, if specified */
  152. STATUS status;           /* status of node: NORMAL, DUMMY, etc. */
  153. LNO level;           /* level number */
  154. int position;           /* position on level */
  155.   /**
  156.      create_node creates a vertex and a node and initializes the
  157.      name, shape, brush, color, attributes, x and y positions, status, level, 
  158.      and position on level.  It returns a pointer to the node.
  159.      If the vertex and node already exist, the values of attributes, shape, 
  160.      etc are changed to the values passed to create_node.
  161.     
  162.      Currently, the level and position are ignored.
  163.    **/
  164. {
  165.     VERTEX *vertex;       /* pointer to vertex */
  166.     NODE *node;           /* pointer to node */
  167.  
  168.     vertex = insert_vertex(digraph, name);
  169.     node = insert_node(digraph, vertex, attr, shape, brush, color, disp,
  170.                   x_pos, y_pos, status);
  171.     return (node);
  172. } /* create_node */
  173.  
  174.  
  175. VERTEX* insert_vertex(digraph, name)
  176. DIGRAPH *digraph;
  177. char *name;       /* name of the vertex to add */
  178.   /**
  179.      insert_vertex returns the pointer to the vertex named name.
  180.      If there is no such vertex, a new one is created.
  181.    **/
  182. {
  183.     short hashcode;        /* hash code for name */
  184.     VERTEX *curvertex;     /* used to chase down the vertex chain */
  185.  
  186.     if (debug)
  187.     {
  188.         printf("insert_vertex:  '%s':  ", name);
  189.     }
  190.  
  191.     hashcode = hash(name);
  192.  
  193.       /* first chase down the list, if any */
  194.     for (curvertex = digraph->hashtbl[hashcode];
  195.          (curvertex != NULL) && (strcmp(curvertex->name, name) != 0);
  196.          curvertex = curvertex->next)
  197.     {}
  198.  
  199.     if (curvertex != NULL)            /* found it */
  200.     {
  201.         if (debug)
  202.     {
  203.         printf("found '%s'\n", curvertex->name);
  204.     }
  205.  
  206.         return (curvertex);
  207.     }
  208.  
  209.     if (debug)
  210.     {
  211.         if (digraph->hashtbl[hashcode] == NULL)    /* start the vertex chain */
  212.     {
  213.         printf("started a chain.\n");
  214.     }
  215.         else                   /* add to the head of the chain */
  216.     {
  217.         printf("added to chain.\n");
  218.     }
  219.     }
  220.  
  221.     new(curvertex, VERTEX);       /* link in a new vertex */
  222.     curvertex->next = digraph->hashtbl[hashcode];
  223.     digraph->hashtbl[hashcode] = curvertex;
  224.     strsave(curvertex->name, name);
  225.     curvertex->vno = -1;     /* no node number assigned yet */
  226.     return (curvertex);
  227. } /* insert_vertex */
  228.  
  229. NODE *insert_node(digraph, vertex, attr, shape, brush, color, disp, 
  230.     x_pos, y_pos, status)
  231. DIGRAPH *digraph;
  232. VERTEX *vertex;   /* vertex info */
  233. char **attr;      /* user-defined attributes for the node */
  234. SHAPE shape;      /* shape of node */
  235. BRUSH brush;      /* how to draw it */
  236. COLOR color;      /* color to draw it */
  237. BOOL disp;      /* display it or not */
  238. int x_pos, y_pos; /* x and y positions */
  239. STATUS status;      /* type of node */
  240.   /** 
  241.      adds a node to digraph.  The new vertex number is put into vertex->vno,
  242.      and the pointer to the node is returned.
  243.      If the node already exists, its attributes, shape, etc are updated.
  244.    **/
  245. {
  246.     NODE *node;     /* pointer to the new node */
  247.  
  248.     if (++digraph->lastnode == MAXNODES)
  249.     {
  250.         PrintError("insert_node:  Too many nodes");
  251.         return (NULL);
  252.     }
  253.  
  254.     if (vertex->vno == -1)    /* new vertex, need to create node */
  255.     {
  256.         new(node, NODE);
  257.         digraph->nodes[digraph->lastnode] = node;
  258.         vertex->vno = digraph->lastnode;
  259.         node->vertex = vertex;
  260.         node->coalescer_vno = -1;
  261.     node->coalesced = FALSE;
  262.     node->coalescer = FALSE;
  263.         node->out_edges = NULL;
  264.         node->in_edges = NULL;
  265.     node->attributes = attr;
  266.     init_set(Expansion(node));
  267.         init_set(Succ_set(node));
  268.         init_set(Ante_set(node));
  269.         init_member(Node_member(node));
  270.     }
  271.     else            /* existing vertex, reuse node */
  272.     {
  273.         node = Node(digraph, vertex->vno);
  274.  
  275.         dispose_attr(node->attributes, NNodeAttr(digraph));
  276.     node->attributes = attr;
  277.     }
  278.   
  279.     X_position(node) = x_pos;
  280.     Y_position(node) = y_pos;
  281.     Shape(node) = shape;
  282.     Brush(node) = brush;
  283.     Color(node) = color;
  284.     Status(node) = status;
  285.     Displayed(node) = disp;
  286.  
  287.       /** 
  288.      The half_width and half_height of the node depend on the shape and on
  289.          the length of the "Text".  The following formulas are preliminary.
  290.        **/
  291.     switch (shape)
  292.     {
  293.         case POINT:
  294.             Half_width(node) = DUMMY_HALF_WIDTH;
  295.             Half_height(node) = 0;
  296.         break;
  297.  
  298.         case DIAMOND:
  299.             Half_width(node) = Node_half_width(node) + HALF_CHAR * 2;
  300.           /* 2 extra chars to avoid pinching chars at the end */
  301.             Half_height(node) = NODE_HALF_HEIGHT + 2;
  302.         break;
  303.  
  304.         case CIRCLE:
  305.             Half_width(node) = Node_half_width(node);
  306.             Half_height(node) = NODE_HALF_HEIGHT + 2;
  307.           /* circle drawing routines should know to make it a circle. */
  308.         break;
  309.  
  310.         case OVAL:
  311.             Half_width(node) = Node_half_width(node);
  312.             Half_height(node) = NODE_HALF_HEIGHT + 2;
  313.         break;
  314.  
  315.         case DOUBLE_BOX:
  316.         case RECTANGLE:
  317.             Half_width(node) = Node_half_width(node);
  318.             Half_height(node) = NODE_HALF_HEIGHT;
  319.         break;
  320.  
  321.         default:
  322.         PrintError("insert_node:  illegal shape");
  323.         break;
  324.     }
  325.  
  326.     return (node);
  327. } /* insert_node */
  328.  
  329. init_member(member)
  330. MEMBER *member;
  331.   /* init_member initializes the fields in member.  */
  332. {
  333.     Last_dummy(member) = 0;      /* has no dummies yet */
  334.     Level_no(member) = -1;       /* no level yet */
  335.     Position(member) = -1;       /* no position on level yet */
  336.     Status(member) = NORMAL;
  337.     Is_layed(member) = FALSE;    /* not layed out yet */
  338.     Bc(member, UP) = Bc(member, DOWN) = NO_BC;
  339.     Priority(member, UP) = Priority(member, DOWN) = 0;
  340.     Prev_member(member) = Next_member(member) = NULL;
  341. } /* init_member */
  342.  
  343. int create_edge(digraph, from_name, to_name, attr, brush, color, reverse)
  344. DIGRAPH *digraph;
  345. char *from_name, *to_name; /* names of from and to nodes */
  346. char **attr;           /* user-defined attributes for edge */
  347. BRUSH brush;           /* how to draw it */
  348. COLOR color;           /* color to draw it */
  349. BOOL reverse;           /* reverse the edge */
  350.   /** 
  351.      create_edge adds the edge from from_name to to_name with attributes attr
  352.      to digraph->.  If from_name or to_name do not exist, an error message
  353.      is printed and the procedure returns a non-zero integer value.
  354.      This procedure checks for valid names and then calls insert_edge.
  355.    **/
  356. {
  357.     VNO from_vno, to_vno;    /* from and to vertex numbers */
  358.     int errval;            /* non-zero if error */
  359.  
  360.     from_vno = get_vno(digraph, from_name);
  361.  
  362.     if (from_vno == -1)
  363.     {
  364.         sprintf(message, "create_edge:  From Node \"%s\" not defined", 
  365.         from_name);
  366.         PrintError(message);
  367.         return (-1);
  368.     }
  369.  
  370.     to_vno = get_vno(digraph, to_name);
  371.  
  372.     if (to_vno == -1)
  373.     {
  374.         sprintf(message, "create_edge:  To Node \"%s\" not defined", to_name);
  375.         PrintError(message);
  376.         return (-1);
  377.     }
  378.  
  379.       /* reverse the edge, but only if these are 'real' nodes */
  380.     if (reverse && !Is_dummy(Node(digraph, to_vno)) && 
  381.     !Is_dummy(Node(digraph, from_vno)))
  382.     {
  383.         errval = insert_edge(digraph, to_vno, from_vno, attr, brush, color);
  384.     reverse_edge(digraph, to_vno, from_vno, 
  385.              max_edges(Node(digraph, to_vno),
  386.                    Node(digraph, from_vno)));
  387.     }
  388.     else
  389.     {
  390.         errval = insert_edge(digraph, from_vno, to_vno, attr, brush, color);
  391.     }
  392.  
  393.     return (errval);
  394. } /* create_edge */
  395.  
  396. int insert_edge(digraph, from_vno, to_vno, attr, brush, color)
  397. DIGRAPH *digraph;
  398. VNO from_vno, to_vno;
  399. char **attr;
  400. BRUSH brush;           /* how to draw it */
  401. COLOR color;           /* color to draw it */
  402.   /** 
  403.      insert_edge adds the edge from from_vno to to_vno with attributes attr
  404.      to digraph->.  If the status of the nodes containing the edge is invalid,
  405.      a non-zero integer value is returned.
  406.      Edges from a node to itself are disallowed.
  407.    **/
  408. {
  409.     NODE *from_node, *to_node;
  410.     int ord;
  411.  
  412.     from_node = Node(digraph, from_vno);
  413.     to_node = Node(digraph, to_vno);
  414.  
  415.     if (from_vno == to_vno)
  416.     {
  417.     fprintf(stderr, 
  418.         "Cannot add edge from a node to itself: Edge %s %s ignored\n", 
  419.         Name(from_node), Name(from_node));
  420.         return (-1);
  421.     }
  422.  
  423.       /**
  424.      change the width of the nodes if necessary to make room for all
  425.      the edges 
  426.        **/
  427.     ord = max_edges(from_node, to_node) + 1;
  428.     fix_width(from_node, ord);
  429.     fix_width(to_node, ord);
  430.  
  431.       /**
  432.      out and in edges are only added between normal nodes.
  433.      Dummy nodes just have successor and predecessor sets.
  434.      Coalescer nodes also have just successor and predecessor sets,
  435.      but we don't need to worry about them here because you can't add
  436.      an edge to/from a coalescer node.
  437.      In essence, there is a distinction between the in and out edges,
  438.      which correspond to the abstract graph, and the predecessor and
  439.      successor sets, which correspond to the displayed graph.  In most 
  440.      cases, the predecessor and successor sets should be directly 
  441.      accessed, while the in and out edges are accessed only indirectly,
  442.      usually by routines in util.c.
  443.        **/
  444.     if (Status(from_node) == NORMAL && Status(to_node) == NORMAL)
  445.     {
  446.         add_out_edge(from_node, attr, brush, color, to_vno, ord);
  447.         add_in_edge(to_node, from_vno, ord);
  448.         add_element(from_node->succ_set, to_vno);
  449.         add_element(to_node->ante_set, from_vno);
  450.     }
  451.     else if (Is_dummy(from_node) || Is_dummy(to_node))
  452.     {
  453.         add_element(from_node->succ_set, to_vno);
  454.         add_element(to_node->ante_set, from_vno);
  455.     }
  456.     else
  457.     {
  458.         sprintf(message, "insert_edge: Illegal status in node %s or %s",
  459.            Name(from_node), Name(to_node));
  460.         PrintError(message);
  461.         return (-1);
  462.     }
  463.  
  464.     return (0);
  465. } /* insert_edge */
  466.  
  467. fix_width(node, ord)
  468. NODE *node;
  469. int ord;
  470.   /* make sure this node has enough room for ord edges */
  471. {
  472.     Half_width(node) = MAX(EDGE_GAP * ord / 2, Half_width(node));
  473. }
  474.  
  475. add_out_edge(from_node, attr, brush, color, to_vno, ord)
  476. NODE *from_node;   /* node with the edge list */
  477. char **attr;       /* user-defined attributes for the edge */
  478. BRUSH brush;       /* how to draw it */
  479. COLOR color;       /* color to draw it */
  480. VNO to_vno;        /* vertex number of target */
  481. int ord;       /* this is the ordth edge from from_node to to_vno */
  482.   /** 
  483.      add_out_edge adds an edge to out_edges.
  484.    **/
  485. {
  486.     OUTEDGE *curedge;    /* the new edge */
  487.  
  488.     new(curedge, OUTEDGE);         /* link in a new edge */
  489.     curedge->next = from_node->out_edges;
  490.     from_node->out_edges = curedge;
  491.  
  492.     Brush(curedge) = brush;
  493.     Color(curedge) = color;
  494.     curedge->attributes = attr;
  495.     curedge->edge_reversed = FALSE;
  496.     curedge->to_vno = to_vno;
  497.     curedge->ordinality = ord;
  498. } /* add_out_edge */
  499.  
  500. add_in_edge(to_node, from_vno, ord)
  501. NODE *to_node;     /* node with the incoming edge list */
  502. VNO from_vno;      /* vertex number of source node */
  503. int ord;       /* this is the ordth edge from from_node to to_vno */
  504.   /**
  505.      add_in_edge adds an edge to in_edges.  Note that all the attributes
  506.      for an edge are kept in the outedges, to save space and make updates
  507.      simpler
  508.    **/
  509. {
  510.     INEDGE *curedge;    /* the new edge */
  511.  
  512.     new(curedge, INEDGE);         /* link in a new edge */
  513.     curedge->next = to_node->in_edges;
  514.     to_node->in_edges = curedge;
  515.  
  516.     curedge->edge_reversed = FALSE;
  517.     curedge->from_vno = from_vno;
  518.     curedge->ordinality = ord;
  519. } /* add_in_edge */
  520.  
  521. VNO get_vno(digraph, name)
  522. DIGRAPH *digraph;
  523. char *name;       /* name of the vertex to search for */
  524.   /** 
  525.      get_vno returns the vertex number for the vertex named name.
  526.      If there is no such vertex, the value -1 is returned.
  527.    **/
  528. {
  529.     short hashcode;        /* hash code for name */
  530.     VERTEX *curvertex;     /* used to chase down the vertex chain */
  531.  
  532.     hashcode = hash(name);
  533.  
  534.       /* first chase down the list, if any */
  535.     for (curvertex = digraph->hashtbl[hashcode];
  536.          (curvertex != NULL) && (strcmp(curvertex->name, name) != 0);
  537.          curvertex = curvertex->next)
  538.     {}
  539.  
  540.     if (curvertex != NULL)            /* found it */
  541.     {
  542.         return(curvertex->vno);
  543.     }
  544.     else
  545.     {
  546.         return ( (VNO) -1);
  547.     }
  548. } /* get_vno */
  549.  
  550. short hash(name)
  551. char  *name;        /* characters to hash together */
  552.   /** 
  553.      hash returns the hash code for name.
  554.    **/
  555. {
  556.     short i;          /* counter */
  557.     short hashcode;   /* computed hash code */
  558.  
  559.     for (i = 0, hashcode = 0; name[i] != '\0'; hashcode+= name[i], i++)
  560.     {}
  561.  
  562.     hashcode = hashcode % MAXHASH;
  563.     return (hashcode);
  564. } /* hash */
  565.